#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @File  : bags.py
# @Author: shadow
# @Date  : 2019/12/31
# @Desc  :

"""
本周作业内容如下：
假设小偷有一个背包，最多能装20公斤赃物，他闯入一户人家，发现如下表所示的物品。很显然，他不能把所有物品都装进背包，所以必须确定拿走哪些物品，留下哪些物品。
名称	价格（美元）	重量（kg）
电脑	200	        20
收音机	20	        4
钟	    175	        10
花瓶	50	        2
书	    10	        1
油画	90	        9

关于获取最优解 或 使用贪婪发获取满意解
满意解应该是比较适合日常生活使用，高要求的场景当然要使用最优解
背包问题怎么求出最优解的组合，待解决
"""

from collections import namedtuple
from itertools import combinations
import numpy as np

goods = namedtuple("goods", "name, price, weight")
goods_list = []
goods_list.append(goods("电脑", 230, 20))
goods_list.append(goods("收音机", 20, 4))
goods_list.append(goods("钟", 175, 10))
goods_list.append(goods("花瓶", 50, 3))
goods_list.append(goods("书", 8, 1))
goods_list.append(goods("油画", 80, 4))

bag_capacity = 10
print(goods_list)


# 死方法，列出所有可能,获取最大价值组合
def bag_all():
    max_value = 0
    max_list = []
    # for i in range(1, len(goods_list)+1):
    for i in range(2, len(goods_list)):  # 如果是20，一眼看出只能一样东西的价值肯定不是最大的，全部拿也是不可能的，从2开始
        for j in combinations(goods_list, i):   # 列出排列组合情况
            value = 0
            weight = 0
            for k in j:
                value += k.price
                weight += k.weight
                if weight >= bag_capacity:
                    break

            if weight <= bag_capacity and value > max_value:
                max_value = value
                max_list = j
    return max_list, max_value


# 贪婪法获取满意解，按照阿静的思路， 最大价值，最小重量，最高性价比排序后，选通过性价比来获取
# 该方法在于迅速找到合适解，并不一定是最优解
def bag_greed():
    goods_tmp = sorted(goods_list, key=lambda x: x.price/x.weight, reverse=True)  # 性价比高排序
    values = 0
    weight = 0
    max_list = []
    for i in goods_tmp:
        if weight + i.weight <= bag_capacity:
            max_list.append(i)
            weight += i.weight
            values += i.price
    return max_list, values


# 0-1背包问题最优解
# 解决思路：动态规划，对每一件物品遍历背包容量，当背包可容纳值大于等于当前物品，与之前已放进去的物品所得价值进行对比，考虑是否需要置换
# 假设有N件物品，背包容量为V，放入第i 件物品耗费的费用是Ci，得到的价值是Wi
# 关键方程： F[i, V] = max{F[i-1,V], F[i-1, V-Ci]+wi}, 解析如下：
'''
可以理解为"将前i 件物品放入容量为v 的背包中"这个子问题，
若只考虑第i 件物品的策略（放或不放），那么就可以转化为一个只和前i - 1 件物品相关的问题。
如果不放第i 件物品，那么问题就转化为“前i -1 件物品放入容量为v 的背包中”，价值为F[i - 1; v]；
如果放第i 件物品，那么问题就转化为“前i - 1 件物品放入剩下的容量为v - Ci 的背包中”，此时能获得的最大价值就是F[i - 1; v - Ci] 再加上通过放入第i 件物品获得的价值Wi
'''
def bag_0_1(weight, value, num):  # return max value
    bag = np.zeros((num+1, bag_capacity+1), dtype=np.int32)  # 列出所有可能，多加的
    bag_list = [False for _ in range(num)]
    for i in range(1, num+1):  # 遍历可以装的物品
        for j in range(1, bag_capacity+1):     # 遍历背包容量
            if weight[i-1] <= j:  # 当前背包容量可以装该物品
                bag[i][j] = max(bag[i - 1][j - weight[i-1]] + value[i-1], bag[i - 1][j])    # 第三种情况，比较值获取较大者
            else:   # 装不下，第二种情况
                bag[i][j] = bag[i - 1][j]
    # print(bag)
    j = bag_capacity
    for i in range(num, 0, -1):
        if bag[i][j] > bag[i - 1][j]:
            bag_list[i-1] = True
            j -= weight[i-1]

    return [goods_list[i] for i in range(num) if bag_list[i]], bag[-1][-1]   # 返回最后一个值，也就是最大值和对应的组合


# 空间优化，尾部迭代，每个状态表示上一次的最佳结果
# F[v] =max｛fF[v], F[v - Ci] +Wi｝
# v 递减是为了保证第i 次循环中的状态F[i; v] 是由状态F[i - 1, v - Ci] 递推而来
# 为了保证每件物品只选一次，保证在考虑“选入第i 件物品”这件策略时，依据的是一个绝无已经选入第i 件物品的子结果F[i -1, v - Ci]
def bag1(weight, value, num):
    values = [0 for i in range(bag_capacity+1)]     # 存储当前背包容量最优解的值
    # bags = [[0]*num for i in range(capacity+1)]  # 存储当前背包容量最优解的方案
    for i in range(1, num + 1):   # 遍历可以装的物品
        # for j in range(capacity+1):  # 遍历背包容量，完全背包问题
        for j in range(bag_capacity, 0, -1):  # 从最大值量遍历背包容量，01背包
            # 背包总容量够放当前物体，遍历前一个状态考虑是否置换
            if j >= weight[i-1]:
                values[j] = max(values[j - weight[i - 1]] + value[i - 1], values[j])

    #             tmp = values[j-weight[i-1]]+value[i-1]   # 替换后的值
    #             if tmp > values[j]:  # 优于之前的方案，替换
    #                 values[j] = tmp
    #                 bags[j][i-1] = 1
    return values


if __name__ == '__main__':
    print(bag_all())
    print(bag_greed())
    print(bag_0_1([i.weight for i in goods_list], [i.price for i in goods_list], len(goods_list)))
    print(bag1([i.weight for i in goods_list], [i.price for i in goods_list], len(goods_list)))

    """
    逻辑清晰！古德
    """


